package binaryTree.review;
/**
 * 3.7日
* */
public class QuickSort1 {
    public int[] quickSort(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    public void sort(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return;
        }
        int boundaryIndex = partition(nums, lo, hi);
        sort(nums, lo, boundaryIndex - 1);
        sort(nums, boundaryIndex + 1, hi);
    }

    public int partition(int[] nums, int lo, int hi) {
        int boundary = nums[lo];
        int j = lo + 1;
        int k = hi;
        while (j <=k) {
            //todo：多想现实意义　j可以等于ｈｉ
            while (nums[j] <= boundary && j <= hi) {
                j++;
            }
            while (nums[k] > boundary && k > lo) {
                k--;
            }
            if (j > k) {
                break;
            }
            swap(nums, j, k);
        }
        swap(nums, lo, k);
        return k;
    }

    public void swap(int[] nums, int j, int k) {
        int temp = nums[j];
        nums[j] = nums[k];
        nums[k] = temp;
    }

    public static void main(String[] args) {
        QuickSort1 quickSort = new QuickSort1();
        int[] nums = new int[]{2, 5, 3, 2, 4, 1, 6};
        quickSort.quickSort(nums);
        for (int a : nums) {
            System.out.println(a);
        }
    }

}
